package com.example.studyinbetterlogin.utils
import kotlin.math.abs

class Point24 {

    val s = ArrayDeque<String>()
    val ans = ArrayDeque<String>()

    fun toDfs(ns: MutableList<Long>, value: Long): ArrayDeque<String> {
        s.clear()
        ans.clear()
        dfs(ns, value)
        return ans
    }

    private fun dfs(ns: MutableList<Long>, value: Long) {
        // If only one number is left and it equals the target value, return the solution
        if (ns.size == 1) {
            if (ns[0] == value) {
                while (s.isNotEmpty()) {
                    ans.add(s.first())
                    println(s.removeFirst()) // Optional print statement
                }
            }
            return
        }

        // Try all pairs of numbers
        for (i in ns.indices) {
            for (j in i + 1 until ns.size) {
                val a = maxOf(ns[i], ns[j])
                val b = minOf(ns[i], ns[j])

                // Addition
                val ms = ns.toMutableList()
                s.add("${a}+${b}=${a + b}")
                ms.removeAt(j)
                ms.removeAt(i)
                ms.add(a + b)
                dfs(ms, value)
                if (ans.isNotEmpty()) return
                s.removeLast()

                // Subtraction
                s.add("${a}-${b}=${abs(a - b)}")
                ms.clear()
                ms.addAll(ns)
                ms.removeAt(j)
                ms.removeAt(i)
                ms.add(abs(a - b))
                dfs(ms, value)
                if (ans.isNotEmpty()) return
                s.removeLast()

                s.add("${b}-${a}=${abs(b - a)}")
                ms.clear()
                ms.addAll(ns)
                ms.removeAt(j)
                ms.removeAt(i)
                ms.add(abs(b - a))
                dfs(ms, value)
                if (ans.isNotEmpty()) return
                s.removeLast()

                // Multiplication
                s.add("${a}*${b}=${a * b}")
                ms.clear()
                ms.addAll(ns)
                ms.removeAt(j)
                ms.removeAt(i)
                ms.add(a * b)
                dfs(ms, value)
                if (ans.isNotEmpty()) return
                s.removeLast()

                // Division
                if (b != 0L && a % b == 0L) {
                    s.add("${a}/${b}=${a / b}")
                    ms.clear()
                    ms.addAll(ns)
                    ms.removeAt(j)
                    ms.removeAt(i)
                    ms.add(a / b)
                    dfs(ms, value)
                    if (ans.isNotEmpty()) return
                    s.removeLast()
                }
            }
        }
    }
}
